import java.util.LinkedList;




public class DeadLockChecker {
	private static DeadLockChecker deadLockChecker;
	private static Box[][] refMap;
	private static boolean[][] visitedMap;
	private static StaticMap globalMap;
	static LinkedList<Boolean> lockedBoxes;
	
	private DeadLockChecker() {
		globalMap = StaticMap.getStaticMap();
		refMap = new Box[globalMap.boardW][globalMap.boardH];
		visitedMap = new boolean[globalMap.boardW][globalMap.boardH];
		lockedBoxes = new LinkedList<Boolean>();
		visitedCoords = new LinkedList<Coord>();
	}
	
	public static boolean hasDeadlocks(BoxList boxList, Box lastPushedBox) {
	    if (deadLockChecker == null)
	    	deadLockChecker = new DeadLockChecker();		
   
	    distributeBoxes(boxList);
	    
	    boolean isLocked=checkIfLocked(lastPushedBox);
	    
	   if (isLocked) print();
	    
	    
	   cleanBoxes(boxList);
	   cleanVisitedCoord();
	    
	   return isLocked;
	    
	 }
	
	
	private static boolean isBoxOnTile(Coord c) {
		return (refMap[c.x][c.y] != null);
	}
	
	private static boolean isFree(char direction) {
	    switch(direction) {
	    case 'U':
	    case 'D':
	    	if (!isBoxOnTile(WalkingCoord.getWest()) && (!globalMap.isTileWall(WalkingCoord.getCurrent())))  {
		    	if (!isBoxOnTile(WalkingCoord.getEast()) && (!globalMap.isTileWall(WalkingCoord.getCurrent())))  {
		    	    WalkingCoord.getInitial(); 
		    		return true;
		    	}
	    	}
	    	break;
	    case 'L':
	    case 'R':
	    	if (!isBoxOnTile(WalkingCoord.getNorth()) && (!globalMap.isTileWall(WalkingCoord.getCurrent())))  {
		    	if (!isBoxOnTile(WalkingCoord.getSouth()) && (!globalMap.isTileWall(WalkingCoord.getCurrent())))  {
		    	    WalkingCoord.getInitial(); 
		    		return true;
		    	}
	    	}
	    	break;
	    default: System.err.println("Illegal direction");
	    }
	    WalkingCoord.getInitial(); 
	    return false;
	}
	
	private static boolean checkTileFreeInDirection(char direction) {

		if (WalkingCoord.currentState() != 0) System.err.println("Error, checkTileFreeInDirection: Must set WalkingCoord to initial state");
		
		/*if (globalMap.isTileWall(WalkingCoord.getFromDirection(direction))) {
			WalkingCoord.getFromDirectionRev(direction);
			WalkingCoord.setCurrentCoordToInitial();
			return false;
		}*/
		
		//Box box = getBoxOnTile(WalkingCoord.getCurrent());
		Box box = getBoxOnTile(WalkingCoord.getFromDirection(direction));
		WalkingCoord.setCurrentCoordToInitial();
		
	    if (box != null) {
	    	
	    	//System.out.println("foudn box: " + direction);
	    	//box.getCoord().print(); print();
	    	
	    	WalkingCoord.setCurrentCoordToInitial();
	    	if (isFree(direction)) {
		    	WalkingCoord.getFromDirectionRev(direction);
		    	WalkingCoord.setCurrentCoordToInitial();		
	    		return true;
	    	}
	    	WalkingCoord.getFromDirectionRev(direction);
	    	WalkingCoord.setCurrentCoordToInitial();
	    	lockedBoxes.add(globalMap.isTileGoal(box.getCoord()));
	    	return false;
	    }
		WalkingCoord.getFromDirectionRev(direction);
		WalkingCoord.setCurrentCoordToInitial();
		return true;
	}
	
	private static char getOrthogonalDir(char dir) {
		switch(dir) {
			case 'u': return 'r';
			case 'r': return 'd';
			case 'd': return 'l';
			case 'l': return 'u';
			case 'U': return 'R';
			case 'R': return 'D';
			case 'D': return 'L';
			case 'L': return 'U';
		}
		return 'x';
	}
	
	private static char getOppositeDir(char dir) {
		switch(dir) {
			case 'u': return 'd';
			case 'r': return 'l';
			case 'd': return 'u';
			case 'l': return 'r';
			case 'U': return 'D';
			case 'R': return 'L';
			case 'D': return 'U';
			case 'L': return 'R';
		}
		return 'x';
	}
	
	
	private static boolean isCornerDeadLock(Coord c, char pushDirection) {
		
		
		for (char direction : Constants.getAllDirections()) {
			WalkingCoord.set(c);
			if (globalMap.isTileCorner(WalkingCoord.getFromDirection(direction))) {
				
				int numOfBoxes = 0;
				WalkingCoord.setCurrentCoordToInitial();
				for (int j=0 ; j<4 ; j++) {
					if (isBoxOnTile(WalkingCoord.getNext())) {
						if (globalMap.isAdjacentToWallTile(WalkingCoord.getCurrent())) {
							numOfBoxes++;
							if (numOfBoxes == 2) return true;
						}
					}
				}
			}
		}
		
		return false;
	}
	
	public static boolean hasAtomicDeadlocks(BoxList boxList, Box lastPushedBox, char pushDirection) {
	    if (deadLockChecker == null)
	    	deadLockChecker = new DeadLockChecker();		
   
	    	
	    distributeBoxes(boxList);
	    
	    boolean isLocked = false;
	    
	    //Check if first box is free

	    
	    WalkingCoord.set(lastPushedBox.getCoord());
	    
	    char orthDir = getOrthogonalDir(pushDirection);	    

	    if (isFree(pushDirection)||isFree(orthDir)) {
	    	//print();
		    cleanBoxes(boxList);
	    	return false;
	    }
	    
	    lockedBoxes.add(globalMap.isTileGoal(lastPushedBox.getCoord()));

	    
	    //Check the box in front of the first box
	    isLocked = isLocked || !checkTileFreeInDirection(pushDirection);

	    
	    //if (isLocked) print();
	    //Check the two boxes on the side of the first box
	   
	    
	    isLocked = isLocked || !checkTileFreeInDirection(orthDir);	   

	    isLocked = isLocked || !checkTileFreeInDirection(getOppositeDir(orthDir));


	    

	    
	    

	    //Check that all locked boxes are on goal tiles
	    boolean b;
	    
	    if (isLocked) { //ny kod
	    	isLocked = false;
		    while(!lockedBoxes.isEmpty()) {
		    	b = lockedBoxes.removeFirst();
		    	if (!b) {
		    		lockedBoxes.clear();
		    		isLocked = true;
		    		break;
		    	}
		    }
	    }
	    lockedBoxes.clear();
	    //if (isLocked) print();
	    
	    if (false&&isLocked) {
	    	
	    	System.out.println("DEADLOCK");
	    	print();
	    	lastPushedBox.getCoord().print();
	    	System.out.println(pushDirection);
	    	System.out.println();
	    }
	    
	    WalkingCoord.set(lastPushedBox.getCoord());
	    
	    /*if (isCornerDeadLock(lastPushedBox.getCoord(), pushDirection)) {
	    	print();
	    	cleanBoxes(boxList);
	    	return true;
	    }*/
	//    if(isLocked) print();
	    
	    cleanBoxes(boxList);
	    
	    return isLocked;
	}
	
	
	private static boolean checkIfLocked(Box lastPushedBox) {
	    //Rule: Box is movable if:
	    //Surrounded vert/horiz by free tiles.

	   boolean isLocked= isLocked(lastPushedBox.getCoord());
	
	    
	    boolean b;
	    
	    if (isLocked) { //ny kod
	    	isLocked = false;
		    while(!lockedBoxes.isEmpty()) {
		    	b = lockedBoxes.removeFirst();
		    	if (!b) {
		    		lockedBoxes.clear();
		    		isLocked = true;
		    		break;
		    	}
		    }
	    }
	    return isLocked;
	}
	
	private static void cleanVisitedCoord(){
		
		 for (Coord c : visitedCoords) {
		    	visitedMap[c.x][c.y] = false;
		    }
		
	}

	public static void distributeBoxes(BoxList boxList) {
		Coord boxCoord;
	    for (Box box : boxList) {
	    	boxCoord = box.getCoord();
	    	refMap[boxCoord.x][boxCoord.y] = box;
	    }
	}
	
	private static void cleanBoxes(BoxList boxList){
		Coord boxCoord;
		for (Box box : boxList) {
	    	boxCoord = box.getCoord();
	    	refMap[boxCoord.x][boxCoord.y] = null;
	    	visitedMap[boxCoord.x][boxCoord.y] = false;
	    }
		
	}
	
	
	public static void print() {
		for (int i=0; i<globalMap.boardH ; i++) {
			System.out.println();
			for (int j=0 ;  j<globalMap.boardW ; j++) {
				if (globalMap.isTileWall(new Coord(j,i))) {
					System.out.print("# ");
				} else if (refMap[j][i] != null) {
					System.out.print("x ");
				} else {
					System.out.print(". ");
				}
			}
		}
		System.out.println();
	}
	
	
	
	public static void fillBoxMatrix(BoxList boxList) {
	    if (deadLockChecker == null)
	    	deadLockChecker = new DeadLockChecker();	
	    
		Coord boxCoord;
	    for (Box box : boxList) {
	    	boxCoord = box.getCoord();
	    	refMap[boxCoord.x][boxCoord.y] = box;
	    }
	}
	
	public static Box getBoxOnTile(Coord c) {
		return refMap[c.x][c.y];
	}
	
	public static void emptyBoxMatrix(BoxList boxList) {
		Coord boxCoord;
	    for (Box box : boxList) {
	    	boxCoord = box.getCoord();
	    	refMap[boxCoord.x][boxCoord.y] = null;
	    }
	}
	
	//==============================================
	//Idea: Fill corner tiles with fake boxes on creation movement (of this class)
	//=============================================
	static LinkedList<Coord> visitedCoords;
	
	

	
	
	
	private static boolean isLocked(Coord currentCoord) {
		
		if ((visitedMap[currentCoord.x][currentCoord.y])) return true;
		
		if (getBox(currentCoord) == null) {
			if (globalMap.isTileWall(currentCoord)) return true;
			

			if (globalMap.isTileCorner(currentCoord)) {
				

				//==============================================
				//Mark Corner as visited
				//==============================================
				
				visitedMap[currentCoord.x][currentCoord.y] = true;
				visitedCoords.add(currentCoord);

				
				//==============================================
				//Time for recursion: If any of the surrounding tiles is not locked. Return false.
				//=============================================
				

				
		    	///return true if everyone is locked
				return ((isLocked(currentCoord.getEastCoord())&&isLocked(currentCoord.getWestCoord()))&&
						(isLocked(currentCoord.getNorthCoord())&&isLocked(currentCoord.getSouthCoord())));
				
			}
			
			if (false&&globalMap.isTileEmpty(currentCoord)) {

				Coord cN = currentCoord.getNorthCoord();
				Coord cS = currentCoord.getSouthCoord();
				Coord cW = currentCoord.getWestCoord();
				Coord cE = currentCoord.getEastCoord();
				
		    	int i=0;
		    	if (getBox(cN) != null) 
		    		i++;
		    	if (getBox(cS) != null)  
			    	i++;
				if (getBox(cW) != null) 
					i++;
				if (getBox(cE) != null) 
					i++;
				
				if (i == 4) {
					return ((isLocked(cE)&&isLocked(cW)))&&
							(isLocked(cN)&&isLocked(cS));
				} else {
					return false;
				}
			}
			//We know that the tile is empty!
			return false;
		}
		

    	visitedCoords.add(currentCoord);
    	visitedMap[currentCoord.x][currentCoord.y] = true;

	    
    	Coord c = currentCoord;
    	
    	boolean horizBlocked = (isLocked(c.getEastCoord())||isLocked(c.getWestCoord()));
    	boolean vertBlocked = (isLocked(c.getNorthCoord())||isLocked(c.getSouthCoord()));	    
    	
    	
    	boolean isLocked = (horizBlocked && vertBlocked);   	
    	
    	
    	if (isLocked) lockedBoxes.add(globalMap.isTileGoal(c));
    	
    	return isLocked;
	 }
	

	private static Box getBox(Coord c) {
		return refMap[c.x][c.y];
	}
	
	private static Box getPotentialBlockingBox(Coord c) {
		if (!globalMap.isTileEmpty(c)) return null;
		return refMap[c.x][c.y];
	}

	
	//Pseudo-wall
	/*
	if (globalMap.isTileGoal(currentCoord)) {
    	if (bE != null)
    		isLocked = isLocked || isLocked(bE, c.getEastCoord());
    	if (bW != null)
    		isLocked = isLocked || isLocked(bW, c.getWestCoord());
    	if (bN != null)
    		isLocked = isLocked || isLocked(bN, c.getNorthCoord());
    	if (bS != null)
    		isLocked = isLocked || isLocked(bS, c.getSouthCoord());
    	return isLocked;
	}*/
	
}
